|
|
Řešení hry Battleship Solitaire pomocí celočíselného programování
Přibylová, Lenka ; Jablonský, Josef (vedoucí práce) ; Fábry, Jan (oponent)
Bakalářská práce se zabývá logickou hrou Battleship Solitaire. Seznamuje čtenáře s historií této hry a s jejími pravidly, ze kterých následně vychází formulace hry jako úlohy celočíselného programování. Vytvořeny jsou dva matematické modely, založené na odlišných přístupech; "cell-based" model je založený na zkoumání jednotlivých polí, zatímco "ship-based" model je založený na kombinaci mřížek obsahujících právě jednu loď. Pro ověření, zda je řešení hry jedinečné, jsou do modelů přidány účelové funkce. Oba modely jsou převedeny do modelovacího systému LINGO, a řešeny pro různé rozměry herní mřížky. Z výsledků testování vyplývá, že "ship-based" model sice pracuje s menším počtem proměnných i omezení, ale je velmi náročný na práci s daty, což řešení velmi zpomaluje, a pro větší rozměry naprosto znemožňuje. Mnohem rychleji byly úlohy vyřešeny pomocí "cell-based" modelu. Řešení bylo nalezeno i pro úlohy s většími rozměry, i když se doba řešení výrazně prodloužila.
|
host ::
RSS.